/*
leetcode 151: 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

 

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
 

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
 

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
*/

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

// 去除多余空格函数
void removeExtraSpaces(string &s) {
    int n = s.size();
    int i = 0, j = 0;

    // 去除前导空格，即把第一个单词前面的空格都删除
    while (i < n && s[i] == ' ') i++;

    // 压缩单词间的多余空格，替换为当个空格
    while (i < n) {
        //当前字符是非空格字符时，保留单词内容的正常逻辑
        if (s[i] != ' ') {
            s[j++] = s[i++]; //将其写入位置 j，然后移动 i 和 j。
        } 
        //当前字符是空格字符时，检查j 指针的前一位，如果 s[j - 1] 是非空格（前一个字符是单词的尾部），
        //保留当前空格，将其写入 j 并移动指针
        else if (j > 0 && s[j - 1] != ' ') {
            s[j++] = s[i++]; //当前 i 写入 j，并移动指针
        } 
        else {
            //如果 s[j - 1] 是空格（当前已经有一个空格），跳过当前字符，直接移动 i，避免写入多余空格。
            i++;
        }
    }

    // 去除尾随空格
    if (j > 0 && s[j - 1] == ' ') j--;

    s.resize(j);//重置 s 的大小为 j 的长度
}

// 主函数：反转字符串中的单词
string reverseWords(string s) {
    // 1. 去除多余空格
    removeExtraSpaces(s);

    // 2. 反转整个字符串
    reverse(s.begin(), s.end());

    // 3. 反转每个单词
    int start = 0, end = 0, n = s.size();
    while (end < n) {
        while (end < n && s[end] != ' ') end++; // 找到单词末尾
        reverse(s.begin() + start, s.begin() + end); // 反转当前单词
        start = ++end; // 移动到下一个单词
    }

    return s;
}

// 测试用例
void runTests() {
    vector<pair<string, string>> testCases = {
        {"   ", ""},
        {"a", "a"},
        {"  hello world  ", "world hello"},
        {"the sky is blue", "blue is sky the"},
        {"  a   good   example  ", "example good a"},
        {"   Alice does not even like bob   ", "bob like even not does Alice"}
    };

    for (const auto &test : testCases) {
        string input = test.first;
        string expected = test.second;
        string result = reverseWords(input);
        cout << "Input: \"" << input << "\"\n";
        cout << "Expected: \"" << expected << "\"\n";
        cout << "Result: \"" << result << "\"\n";
        cout << (result == expected ? "PASS" : "FAIL") << "\n\n";
    }
}

int main() {
    cout << "Running Tests for 'reverseWords':\n\n";
    runTests();
    return 0;
}
